package a07_二叉树;

/**
 * 什么是深度？
 * 节点到根节点的距离
 *
 * 什么是高度？
 * 节点到叶子节点的距离
 *
 * 如何求高度？
 * 后序
 * 知道了下面，上面的+1就行了
 *
 *
 * 如何求深度？
 * 前序
 * 知道了上面，下面的+1就行了
 *
 *
 * 此题求二叉树的最小深度
 * 跟节点到叶子节点的最小距离 => 根节点的最小高度
 *
 *
 *
 *
 *
 * @author flyduck
 * @since 2024-08-28
 */
public class a10_二叉树的最小深度 {

    //    3
    // 9     20
    //     15    7

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(2,null,new TreeNode(3, null, new TreeNode(4, null, new TreeNode(5, null, new TreeNode(6)))));
        int i = minDepth(treeNode);
    }

    public static int minDepth(TreeNode root) {
        return getMinHeight(root);
    }

    private static int getMinHeight(TreeNode node) {
        if(node == null){
            return 0;
        }
        int leftMinHeight = getMinHeight(node.left);
        int rightMinHeight = getMinHeight(node.right);
        if(node.left == null && node.right != null){
            return rightMinHeight + 1;
        }
        if(node.left != null && node.right == null){
            return leftMinHeight + 1;
        }

        return Math.min(leftMinHeight, rightMinHeight) + 1;
    }
}
